package labuladong.第四章;

import leetcode.Head;
import leetcode.ListNode;

public class ReverseList {

    public static void main(String[] args) {
        ListNode node = Head.genList();
        ListNode head = reverseGroup(node, 2);
        ListNode.printList(head);
    }

    /**
     * 完全反转
     * @param a
     * @return
     */
    public static ListNode reverse01(ListNode a) {
        ListNode pre = null;
        ListNode cur = a;
        ListNode next = a;
        while (cur != null) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }

    /**
     * 反转[a, b)区间内
     * @param a
     * @param b
     * @return
     */
    public static ListNode reverse02(ListNode a, ListNode b) {
        ListNode pre = null;
        ListNode cur = a;
        ListNode next = b;
        while (cur != b) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }

    public static ListNode reverseGroup(ListNode head, int k) {
        if(head == null) {
            return null;
        }

        ListNode a, b;
        a = b = head;
        for (int i=0; i<k; i++) {
            // 不⾜ k 个，不需要反转，base case
            if (b==null) {
                return head;
            }
            b = b.next;
        }

        // 反转前 k 个元素
        ListNode newHead = reverse02(a, b);
        // 递归反转后续链表并连接起来
        a.next = reverseGroup(b, k);
        return newHead;
    }
}
